class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int n = s.size();
        string t;
        for(int i = n - 1; i >= 0; i--)t += s[i];//将 s 翻转得到 t
        vector<vector<int>>dp(n, vector<int>(n, 0));
        dp[0][0] = (int)(s[0] == t[0]); //初始化
        for(int i = 1; i < n; i++){
            dp[i][0] = (s[i] == t[0] ? 1 : dp[i - 1][0]);
            dp[0][i] = (s[0] == t[i] ? 1 : dp[0][i - 1]);
        }
        for(int i = 1; i < n; i++){ //求最长公共子序列
            for(int j = 1; j < n; j++){
                if(s[i] == t[j])dp[i][j] = dp[i - 1][j - 1] + 1;
                else dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
            }
        }
        return dp[n - 1][n - 1];
    }
};

/**
 * 2021.9.12
 * 可以把原字符串翻转得到新的字符串然后求两串的最长公共子序列
 * 等价于该问题。
 */